//
//  LeetcodeQuestions.hpp
//  CppDemo
//
//  Created by 蒋益杰 on 16/9/9.
//  Copyright © 2016年 com.ed. All rights reserved.
//

#ifndef LeetcodeQuestions_hpp
#define LeetcodeQuestions_hpp

#include <stdio.h>
#include <string>
#include <vector>

#include "STLUsage.hpp"

using namespace std;

struct RandomListNode {
    int label;
    RandomListNode *next, *random;
    RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
};

struct UndirectedGraphNode {
    int label;
    vector<UndirectedGraphNode *> neighbors;
    UndirectedGraphNode(int x) : label(x) {};
};

bool isNumber(string s);

int getSum(int a, int b);

vector<int> intersection(vector<int>& nums1, vector<int>& nums2);
vector<int> plusOne(vector<int>& digits);

char findTheDifference(string s, string t);

int firstUniqChar(string s);
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB);

vector<string> binaryTreePaths(TreeNode* root);

int computeArea(int A, int B, int C, int D, int E, int F, int G, int H);

void rightshfit(vector<int> &s, int num_to_shift);

vector<int> singleNumber(vector<int>& nums);

string removeDuplicateLetters(string s);

vector<int> rightSideView(TreeNode* root);

RandomListNode *copyRandomList(RandomListNode *head);

TreeNode* sortedListToBST(ListNode* head);

//int findDuplicate(vector<int>& nums);

int findMin(vector<int>& nums);

int splitArray(vector<int>& nums, int m);

class Codec {
public:
    
    // Encodes a tree to a single string.
    string serialize(TreeNode* root);
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data);
    
};

bool isMatch(string s, string p);
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people);
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node);
vector<vector<string>> groupAnagrams(vector<string>& strs);

void replaceBlank(char string[], int length);

void makeNext(const char p[], int next[]);
int kmp(const char src[], const char p[], int next[]);

#pragma mark - tree
bool insert(TreeNode *root, int val);
size_t get_node_count(TreeNode *root);
void print_values(TreeNode *root);
bool delete_tree(TreeNode *root);
bool is_in_tree(TreeNode *root, int val);
int get_height(TreeNode *root);
int get_min(TreeNode *root);
int get_max(TreeNode *root);
bool is_binary_search_tree(TreeNode *root);
bool delete_value(TreeNode *root, int value);
int get_successor(TreeNode *root, int value);
int get_predecessor(TreeNode *root, int value);

#endif /* LeetcodeQuestions_hpp */
